package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-06-28 16:52
 */
public class 题库_0134_加油站 {

  public static void main(String[] args) {
    int[] gas = {5,1,2,3,4};
    int[] cost = {4,4,1,5,1};
    Solution solution = new Solution();
    int circuit = solution.canCompleteCircuit(gas, cost);
    System.out.println(circuit);
  }

  static
  class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
      if (gas == null || gas.length == 0 || cost == null || cost.length == 0) {
        return -1;
      }
      int[] surplus = new int[gas.length];
      int sum = 0;
      for (int i = 0; i < gas.length; ++i) {
        surplus[i] = gas[i] - cost[i];
        sum += surplus[i];
      }
      if (sum < 0) {
        return -1;
      }
      for (int i = 0; i < surplus.length; ++i) {
        if (surplus[i] >= 0) {
          sum = 0;
          for (int j = 0; j < surplus.length; ++j) {
            sum += surplus[(i + j) % surplus.length];
            if (sum < 0) {
              i += j;
              break;
            }
          }
          if (sum >= 0) {
            return i;
          }
        }
      }
      return -1;
    }
  }

}




















